def partition(nums, left, right):
    key = nums[left - 1]
    while left < right:
        while left < right and nums[right - 1] >= key:
            right -= 1
        nums[left - 1], nums[right - 1] = nums[right - 1], nums[left - 1]
        while left < right and nums[left - 1] <= key:
            left += 1
        nums[left - 1], nums[right - 1] = nums[right - 1], nums[left - 1]
    return left


def QSort(nums, left, right):
    if left < right:
        partition_position = partition(nums, left, right)
        nums = QSort(nums, left, partition_position - 1)
        nums = QSort(nums, partition_position + 1, right)
    return nums


if __name__ == "__main__":
    nums = [50, 50, 90, 30, 70, 40, 80, 60, 20]
    nums = QSort(nums, 1, len(nums))
    print(nums)
    pass
